/*
 * Created on May 8, 2008
 *
 * Copyright (c) 2008, the JUNG Project and the Regents of the University 
 * of California
 * All rights reserved.
 *
 * This software is open-source under the BSD license; see either
 * "license.txt" or
 * http://jung.sourceforge.net/license.txt for a description.
 */
package edu.uci.ics.jung.graph;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.apache.commons.collections15.CollectionUtils;
import org.apache.commons.collections15.Factory;
import org.geogebra.common.util.debug.Log;

import edu.uci.ics.jung.graph.util.EdgeType;
import edu.uci.ics.jung.graph.util.Pair;

/**
 * An implementation of <code>Tree</code> in which each vertex has <= k
 * children. The value of 'k' is specified by the constructor parameter. A
 * specific child (edge) can be retrieved directly by specifying the index at
 * which the child is located. By default, new (child) vertices are added at the
 * lowest index available, if no index is specified.
 * 
 */
@SuppressWarnings("serial")
public class OrderedKAryTree<V, E> extends AbstractTypedGraph<V, E>
		implements Tree<V, E> {
	protected Map<E, Pair<V>> edge_vpairs;
	protected Map<V, VertexData> vertex_data;
	protected int height;
	protected V root;
	protected int order;

	/**
	 * Returns a {@code Factory} that creates an instance of this graph type.
	 * 
	 * @param <V>
	 *            the vertex type for the graph factory
	 * @param <E>
	 *            the edge type for the graph factory
	 */
	public static <V, E> Factory<DirectedGraph<V, E>> getFactory(
			final int order) {
		return new Factory<DirectedGraph<V, E>>() {
			@Override
			public DirectedGraph<V, E> create() {
				return new OrderedKAryTree<V, E>(order);
			}
		};
	}

	/**
	 * Creates a new instance with the specified order (maximum number of
	 * children).
	 */
	public OrderedKAryTree(int order) {
		super(EdgeType.DIRECTED);
		this.order = order;
		this.height = -1;
		this.edge_vpairs = new HashMap<E, Pair<V>>();
		this.vertex_data = new HashMap<V, VertexData>();
	}

	/**
	 * Returns the number of children that {@code vertex} has.
	 * 
	 * @see edu.uci.ics.jung.graph.Tree#getChildCount(java.lang.Object)
	 */
	@Override
	public int getChildCount(V vertex) {
		if (!containsVertex(vertex)) {
			return 0;
		}
		List<E> edges = vertex_data.get(vertex).child_edges;
		if (edges == null) {
			return 0;
		}
		int count = 0;
		for (E edge : edges) {
			count += edge == null ? 0 : 1;
		}

		return count;
	}

	/**
	 * Returns the child edge of the vertex at index <code>index</code>.
	 * 
	 * @param vertex
	 * @param index
	 * @return the child edge of the vertex at index <code>index</code>
	 */
	public E getChildEdge(V vertex, int index) {
		if (!containsVertex(vertex)) {
			return null;
		}
		List<E> edges = vertex_data.get(vertex).child_edges;
		if (edges == null) {
			return null;
		}
		return edges.get(index);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Tree#getChildEdges(java.lang.Object)
	 */
	@Override
	public Collection<E> getChildEdges(V vertex) {
		if (!containsVertex(vertex)) {
			return null;
		}
		List<E> edges = vertex_data.get(vertex).child_edges;
		return edges == null ? Collections.<E> emptySet()
				: CollectionUtils.unmodifiableCollection(edges);
	}

	/**
	 * Returns an ordered list of {@code vertex}'s child vertices. If there is
	 * no child in position i, then the list will contain {@code null} in
	 * position i. If {@code vertex} has no children then the empty set will be
	 * returned.
	 * 
	 * @see edu.uci.ics.jung.graph.Tree#getChildren(java.lang.Object)
	 */
	@Override
	public Collection<V> getChildren(V vertex) {
		if (!containsVertex(vertex)) {
			return null;
		}
		List<E> edges = vertex_data.get(vertex).child_edges;
		if (edges == null) {
			return Collections.emptySet();
		}
		Collection<V> children = new ArrayList<V>(order);
		for (E edge : edges) {
			children.add(this.getOpposite(vertex, edge));
		}
		return CollectionUtils.unmodifiableCollection(children);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Tree#getDepth(java.lang.Object)
	 * @return the depth of the vertex in this tree, or -1 if the vertex is not
	 *         present in this tree
	 */
	@Override
	public int getDepth(V vertex) {
		if (!containsVertex(vertex)) {
			return -1;
		}
		return vertex_data.get(vertex).depth;
	}

	/**
	 * Returns the height of the tree, or -1 if the tree is empty.
	 * 
	 * @see edu.uci.ics.jung.graph.Tree#getHeight()
	 */
	@Override
	public int getHeight() {
		return height;
	}

	/**
	 * @see edu.uci.ics.jung.graph.Tree#getParent(java.lang.Object)
	 */
	@Override
	public V getParent(V vertex) {
		if (!containsVertex(vertex)) {
			return null;
		} else if (vertex.equals(root)) {
			return null;
		}
		return edge_vpairs.get(vertex_data.get(vertex).parent_edge).getFirst();
	}

	/**
	 * @see edu.uci.ics.jung.graph.Tree#getParentEdge(java.lang.Object)
	 */
	@Override
	public E getParentEdge(V vertex) {
		if (!containsVertex(vertex)) {
			return null;
		}
		return vertex_data.get(vertex).parent_edge;
	}

	/**
	 * @see edu.uci.ics.jung.graph.Tree#getRoot()
	 */
	@Override
	public V getRoot() {
		return root;
	}

	/**
	 * @see edu.uci.ics.jung.graph.Forest#getTrees()
	 */
	@Override
	public Collection<Tree<V, E>> getTrees() {
		Collection<Tree<V, E>> forest = new ArrayList<Tree<V, E>>(1);
		forest.add(this);
		return forest;
	}

	/**
	 * Adds the specified {@code child} vertex and edge {@code e} to the graph
	 * with the specified parent vertex {@code parent}. If {@code index} is
	 * greater than or equal to 0, then the child is placed at position
	 * {@code index}; if it is less than 0, the child is placed at the lowest
	 * available position; if it is greater than or equal to the order of this
	 * tree, an exception is thrown.
	 * 
	 * @see edu.uci.ics.jung.graph.Graph#addEdge(java.lang.Object,
	 *      java.lang.Object, java.lang.Object)
	 */
	public boolean addEdge(E e, V parent, V child, int index) {
		if (e == null || child == null || parent == null) {
			throw new IllegalArgumentException("Inputs may not be null");
		}
		if (!containsVertex(parent)) {
			throw new IllegalArgumentException(
					"Tree must already " + "include parent: " + parent);
		}
		if (containsVertex(child)) {
			throw new IllegalArgumentException(
					"Tree must not already " + "include child: " + child);
		}
		if (parent.equals(child)) {
			throw new IllegalArgumentException(
					"Input vertices must be distinct");
		}
		if (index < 0 || index >= order) {
			throw new IllegalArgumentException(
					"'index' must be in [0, [order-1]]");
		}

		Pair<V> endpoints = new Pair<V>(parent, child);
		if (containsEdge(e)) {
			if (!endpoints.equals(edge_vpairs.get(e))) {
				throw new IllegalArgumentException("Tree already includes edge"
						+ e + " with different endpoints "
						+ edge_vpairs.get(e));
			}
			return false;
		}

		VertexData parent_data = vertex_data.get(parent);
		List<E> outedges = parent_data.child_edges;

		if (outedges == null) {
			outedges = new ArrayList<E>(this.order);
		}

		boolean edge_placed = false;
		if (outedges.get(index) != null) {
			throw new IllegalArgumentException(
					"Parent " + parent + " already has a child at index "
							+ index + " in this tree");
		}
		outedges.set(index, e);
		for (int i = 0; i < order; i++) {
			if (outedges.get(i) == null) {
				outedges.set(i, e);
				edge_placed = true;
				break;
			}
		}
		if (!edge_placed) {
			throw new IllegalArgumentException("Parent " + parent + " already"
					+ " has " + order + " children in this tree");
		}

		// initialize VertexData for child; leave child's child_edges null for
		// now
		VertexData child_data = new VertexData(e, parent_data.depth + 1);
		vertex_data.put(child, child_data);

		height = child_data.depth > height ? child_data.depth : height;
		edge_vpairs.put(e, endpoints);

		return true;
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#addEdge(java.lang.Object,
	 *      java.lang.Object, java.lang.Object)
	 */
	@Override
	public boolean addEdge(E e, V parent, V child) {
		return addEdge(e, parent, child, -1);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#addEdge(java.lang.Object,
	 *      java.lang.Object, java.lang.Object,
	 *      edu.uci.ics.jung.graph.util.EdgeType)
	 */
	@Override
	public boolean addEdge(E e, V v1, V v2, EdgeType edge_type) {
		this.validateEdgeType(edge_type);
		return addEdge(e, v1, v2);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#getDest(java.lang.Object)
	 */
	@Override
	public V getDest(E directed_edge) {
		if (!containsEdge(directed_edge)) {
			return null;
		}
		return edge_vpairs.get(directed_edge).getSecond();
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#getEndpoints(java.lang.Object)
	 */
	@Override
	public Pair<V> getEndpoints(E edge) {
		if (!containsEdge(edge)) {
			return null;
		}
		return edge_vpairs.get(edge);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#getInEdges(java.lang.Object)
	 */
	@Override
	public Collection<E> getInEdges(V vertex) {
		if (!containsVertex(vertex)) {
			return null;
		} else if (vertex.equals(root)) {
			return Collections.emptySet();
		} else {
			return Collections.singleton(getParentEdge(vertex));
		}
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#getOpposite(java.lang.Object,
	 *      java.lang.Object)
	 */
	@Override
	public V getOpposite(V vertex, E edge) {
		if (!containsVertex(vertex) || !containsEdge(edge)) {
			return null;
		}
		Pair<V> endpoints = edge_vpairs.get(edge);
		V v1 = endpoints.getFirst();
		V v2 = endpoints.getSecond();
		return v1.equals(vertex) ? v2 : v1;
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#getOutEdges(java.lang.Object)
	 */
	@Override
	public Collection<E> getOutEdges(V vertex) {
		return getChildEdges(vertex);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#getPredecessorCount(java.lang.Object)
	 * @return 0 if <code>vertex</code> is the root, -1 if the vertex is not an
	 *         element of this tree, and 1 otherwise
	 */
	@Override
	public int getPredecessorCount(V vertex) {
		if (!containsVertex(vertex)) {
			return -1;
		}
		return vertex.equals(root) ? 0 : 1;
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#getPredecessors(java.lang.Object)
	 */
	@Override
	public Collection<V> getPredecessors(V vertex) {
		if (!containsVertex(vertex)) {
			return null;
		}
		if (vertex.equals(root)) {
			return Collections.emptySet();
		}
		return Collections.singleton(getParent(vertex));
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#getSource(java.lang.Object)
	 */
	@Override
	public V getSource(E directed_edge) {
		if (!containsEdge(directed_edge)) {
			return null;
		}
		return edge_vpairs.get(directed_edge).getSecond();
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#getSuccessorCount(java.lang.Object)
	 */
	@Override
	public int getSuccessorCount(V vertex) {
		return getChildCount(vertex);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#getSuccessors(java.lang.Object)
	 */
	@Override
	public Collection<V> getSuccessors(V vertex) {
		return getChildren(vertex);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#inDegree(java.lang.Object)
	 */
	@Override
	public int inDegree(V vertex) {
		if (!containsVertex(vertex)) {
			return 0;
		}
		if (vertex.equals(root)) {
			return 0;
		}
		return 1;
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#isDest(java.lang.Object,
	 *      java.lang.Object)
	 */
	@Override
	public boolean isDest(V vertex, E edge) {
		if (!containsEdge(edge) || !containsVertex(vertex)) {
			return false;
		}
		return edge_vpairs.get(edge).getSecond().equals(vertex);
	}

	/**
	 * Returns <code>true</code> if <code>vertex</code> is a leaf of this tree,
	 * i.e., if it has no children.
	 * 
	 * @param vertex
	 *            the vertex to be queried
	 * @return <code>true</code> if <code>outDegree(vertex)==0</code>
	 */
	public boolean isLeaf(V vertex) {
		if (!containsVertex(vertex)) {
			return false;
		}
		return outDegree(vertex) == 0;
	}

	/**
	 * Returns true iff <code>v1</code> is the parent of <code>v2</code>. Note
	 * that if <code>v2</code> is the root and <code>v1</code> is
	 * <code>null</code>, this method returns <code>true</code>.
	 * 
	 * @see edu.uci.ics.jung.graph.Graph#isPredecessor(java.lang.Object,
	 *      java.lang.Object)
	 */
	@Override
	public boolean isPredecessor(V v1, V v2) {
		if (!containsVertex(v2)) {
			return false;
		}
		return getParent(v2).equals(v1);
	}

	/**
	 * Returns <code>true</code> if <code>vertex</code> is a leaf of this tree,
	 * i.e., if it has no children.
	 * 
	 * @param vertex
	 *            the vertex to be queried
	 * @return <code>true</code> if <code>outDegree(vertex)==0</code>
	 */
	public boolean isRoot(V vertex) {
		if (root == null) {
			return false;
		}
		return root.equals(vertex);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#isSource(java.lang.Object,
	 *      java.lang.Object)
	 */
	@Override
	public boolean isSource(V vertex, E edge) {
		if (!containsEdge(edge) || !containsVertex(vertex)) {
			return false;
		}
		return edge_vpairs.get(edge).getFirst().equals(vertex);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#isSuccessor(java.lang.Object,
	 *      java.lang.Object)
	 */
	@Override
	public boolean isSuccessor(V v1, V v2) {
		if (!containsVertex(v2)) {
			return false;
		}
		if (containsVertex(v1)) {
			return getParent(v1).equals(v2);
		}
		return isLeaf(v2) && v1 == null;
	}

	/**
	 * @see edu.uci.ics.jung.graph.Graph#outDegree(java.lang.Object)
	 */
	@Override
	public int outDegree(V vertex) {
		if (!containsVertex(vertex)) {
			return 0;
		}
		List<E> out_edges = vertex_data.get(vertex).child_edges;
		if (out_edges == null) {
			return 0;
		}
		int degree = 0;
		for (E e : out_edges) {
			degree += (e == null) ? 0 : 1;
		}
		return degree;
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#addEdge(java.lang.Object,
	 *      java.util.Collection)
	 */
	@Override
	@SuppressWarnings("unchecked")
	public boolean addEdge(E edge, Collection<? extends V> vertices,
			EdgeType edge_type) {
		if (edge == null || vertices == null) {
			throw new IllegalArgumentException("inputs may not be null");
		}
		if (vertices.size() != 2) {
			throw new IllegalArgumentException(
					"'vertices' must contain " + "exactly 2 distinct vertices");
		}
		this.validateEdgeType(edge_type);
		Pair<V> endpoints;
		if (vertices instanceof Pair) {
			endpoints = (Pair<V>) vertices;
		} else {
			endpoints = new Pair<V>(vertices);
		}
		V v1 = endpoints.getFirst();
		V v2 = endpoints.getSecond();
		if (v1.equals(v2)) {
			throw new IllegalArgumentException(
					"Input vertices must be distinct");
		}
		return addEdge(edge, v1, v2);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#addVertex(java.lang.Object)
	 */
	@Override
	public boolean addVertex(V vertex) {
		if (root == null) {
			this.root = vertex;
			vertex_data.put(vertex, new VertexData(null, 0));
			this.height = 0;
			return true;
		}
		throw new UnsupportedOperationException("Unless you are setting "
				+ "the root, use addEdge() or addChild()");
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#isIncident(java.lang.Object,
	 *      java.lang.Object)
	 */
	@Override
	public boolean isIncident(V vertex, E edge) {
		if (!containsVertex(vertex) || !containsEdge(edge)) {
			return false;
		}
		return edge_vpairs.get(edge).contains(vertex);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#isNeighbor(java.lang.Object,
	 *      java.lang.Object)
	 */
	@Override
	public boolean isNeighbor(V v1, V v2) {
		if (!containsVertex(v1) || !containsVertex(v2)) {
			return false;
		}
		return getNeighbors(v1).contains(v2);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#containsEdge(java.lang.Object)
	 */
	@Override
	public boolean containsEdge(E edge) {
		return edge_vpairs.containsKey(edge);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#containsVertex(java.lang.Object)
	 */
	@Override
	public boolean containsVertex(V vertex) {
		return vertex_data.containsKey(vertex);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#findEdge(java.lang.Object,
	 *      java.lang.Object)
	 */
	@Override
	public E findEdge(V v1, V v2) {
		if (!containsVertex(v1) || !containsVertex(v2)) {
			return null;
		}
		VertexData v1_data = vertex_data.get(v1);
		if (edge_vpairs.get(v1_data.parent_edge).getFirst().equals(v2)) {
			return v1_data.parent_edge;
		}
		List<E> edges = v1_data.child_edges;
		if (edges == null) {
			return null;
		}
		for (E edge : edges) {
			if (edge != null && edge_vpairs.get(edge).getSecond().equals(v2)) {
				return edge;
			}
		}
		return null;
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#findEdgeSet(java.lang.Object,
	 *      java.lang.Object)
	 */
	@Override
	public Collection<E> findEdgeSet(V v1, V v2) {
		E edge = findEdge(v1, v2);
		if (edge == null) {
			return Collections.emptySet();
		}
		return Collections.singleton(edge);
	}

	/**
	 * Returns the child of <code>vertex</code> at position <code>index</code>
	 * in this tree, or <code>null</code> if it has no child at that position.
	 * 
	 * @param vertex
	 *            the vertex to query
	 * @return the child of <code>vertex</code> at position <code>index</code>
	 *         in this tree, or <code>null</code> if it has no child at that
	 *         position
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code>index</code> is not in the range
	 *             {@code [0, order-1]}
	 */
	public V getChild(V vertex, int index) {
		if (index < 0 || index >= order) {
			throw new ArrayIndexOutOfBoundsException(
					index + " is not in [0, order-1]");
		}
		if (!containsVertex(vertex)) {
			return null;
		}
		List<E> edges = vertex_data.get(vertex).child_edges;
		if (edges == null) {
			return null;
		}
		E edge = edges.get(index);
		return edge == null ? null : edge_vpairs.get(edge).getSecond();
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#getEdgeCount()
	 */
	@Override
	public int getEdgeCount() {
		return edge_vpairs.size();
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#getEdges()
	 */
	@Override
	public Collection<E> getEdges() {
		return CollectionUtils.unmodifiableCollection(edge_vpairs.keySet());
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#getIncidentCount(java.lang.Object)
	 */
	@Override
	public int getIncidentCount(E edge) {
		return 2; // all tree edges have 2 incident vertices
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#getIncidentEdges(java.lang.Object)
	 */
	@Override
	public Collection<E> getIncidentEdges(V vertex) {
		if (!containsVertex(vertex)) {
			return null;
		}
		ArrayList<E> edges = new ArrayList<E>(order + 1);
		VertexData v_data = vertex_data.get(vertex);
		if (v_data.parent_edge != null) {
			edges.add(v_data.parent_edge);
		}
		if (v_data.child_edges != null) {
			for (E edge : v_data.child_edges) {
				if (edge != null) {
					edges.add(edge);
				}
			}
		}
		if (edges.isEmpty()) {
			return Collections.emptySet();
		}
		return Collections.unmodifiableCollection(edges);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#getIncidentVertices(java.lang.Object)
	 */
	@Override
	public Collection<V> getIncidentVertices(E edge) {
		return edge_vpairs.get(edge);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#getNeighborCount(java.lang.Object)
	 */
	@Override
	public int getNeighborCount(V vertex) {
		if (!containsVertex(vertex)) {
			return 0;
		}
		return (vertex.equals(root) ? 0 : 1) + this.getChildCount(vertex);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#getNeighbors(java.lang.Object)
	 */
	@Override
	public Collection<V> getNeighbors(V vertex) {
		if (!containsVertex(vertex)) {
			return null;
		}
		ArrayList<V> vertices = new ArrayList<V>(order + 1);
		VertexData v_data = vertex_data.get(vertex);
		if (v_data.parent_edge != null) {
			vertices.add(edge_vpairs.get(v_data.parent_edge).getFirst());
		}
		if (v_data.child_edges != null) {
			for (E edge : v_data.child_edges) {
				if (edge != null) {
					vertices.add(edge_vpairs.get(edge).getSecond());
				}
			}
		}
		if (vertices.isEmpty()) {
			return Collections.emptySet();
		}
		return Collections.unmodifiableCollection(vertices);
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#getVertexCount()
	 */
	@Override
	public int getVertexCount() {
		return vertex_data.size();
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#getVertices()
	 */
	@Override
	public Collection<V> getVertices() {
		return CollectionUtils.unmodifiableCollection(vertex_data.keySet());
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#removeEdge(java.lang.Object)
	 */
	@Override
	public boolean removeEdge(E edge) {
		if (!containsEdge(edge)) {
			return false;
		}

		removeVertex(edge_vpairs.get(edge).getSecond());
		edge_vpairs.remove(edge);

		return true;
	}

	/**
	 * @see edu.uci.ics.jung.graph.Hypergraph#removeVertex(java.lang.Object)
	 */
	@Override
	public boolean removeVertex(V vertex) {
		if (!containsVertex(vertex)) {
			return false;
		}

		// recursively remove all of vertex's children
		for (V v : getChildren(vertex)) {
			removeVertex(v);
		}

		E parent_edge = getParentEdge(vertex);
		edge_vpairs.remove(parent_edge);
		List<E> edges = vertex_data.get(vertex).child_edges;
		if (edges != null) {
			for (E edge : edges) {
				edge_vpairs.remove(edge);
			}
		}
		vertex_data.remove(vertex);

		return true;
	}

	protected class VertexData {
		List<E> child_edges;
		E parent_edge;
		int depth;

		protected VertexData(E parent_edge, int depth) {
			this.parent_edge = parent_edge;
			this.depth = depth;
		}
	}

	@Override
	public boolean addEdge(E edge, Pair<? extends V> endpoints,
			EdgeType edgeType) {
		if (edge == null || endpoints == null) {
			throw new IllegalArgumentException("inputs must not be null");
		}
		return addEdge(edge, endpoints.getFirst(), endpoints.getSecond(),
				edgeType);
	}

	@Override
	public OrderedKAryTree<V, E> newInstance() {
		// TODO Auto-generated method stub
		Log.debug("implementation needed");
		return null;
	}

}
